国防科技大学 编译原理 第5讲 词法分析2

课程主页：

https://www.icourse163.org/course/NUDT-1003101005?tid=1460976445

这次回顾第5讲：词法分析2。

第5讲 词法分析2

词法规则的形式化——正规集和正规式

单词集合、正规集和正规式

• 程序设计语言的单词符号都是一些特殊的字符串
• 用正规集和正规表达式（简称正规式）来描述
  • 正规集可以用正规式表示
  • 正规式是表示正规集一种方法
  • 一个字集合是正规集当且仅当它能用正规式表示

正规式和正规集的递归定义

• 对给定的字母表$Σ$
  • $\varepsilon$和$\varnothing$都是$Σ$上的正规式，它们所表示的正规集为$\{\varepsilon\}$和$\varnothing$;
  • 任何$a∈Σ$，$a$是$Σ$上的正规式，它所表示的正规集为$\{a\}$;
  • 假定$e_1$和$e_2$都是$Σ$上的正规式，它们所表示的正规集为$L(e_1)$和$L(e_2)$，则
    • $(e_1|e_2)$为正规式，它所表示的正规集为$L(e_1)∪L(e_2)$
    • $(e_1.e_2)$为正规式，它所表示的正规集为$L(e_1)L(e_2)$
    • $(e_1)^{\star}$为正规式，它所表示的正规集为$(L(e_1))^{\star}$
  • 仅由有限次使用上述三步骤而定义的表达式才是$Σ$上的正规式，仅由这些正规式表示的字集才是$Σ$上的正规集。
• 对正规式，下列等价成立
  • $e_1|e_2 = e_2|e_1$交换律
  • $e_1 |(e_2|e_3) = (e_1|e_2)|e_3$结合律
  • $e_1(e_2e_3) = (e_1e_2)e_3$结合律
  • $e_1(e_2|e_3) = e_1e_2|e_1e_3$分配律
  • $(e_2|e_3)e_1 = e_2e_1|e_3 e_1$分配律
  • $eε = ε e = e ,e_1e_2 <> e_2 e_1$

正规式的等价性

• 若两个正规式所表示的正规集相同，则称这两个正规式等价。如

  $$b(a b)^{\star}=(b a)^{\star} b$$

• 证明：

  $$\begin{aligned} L(b(ab)^{\star})= &L(b)L((ab)^{\star})\\ = &L(b) (L(ab))^{\star}\\ = &L(b) (L(a)L(b))^{\star}\\ =&\{b\} \{ab\}^{\star}\\ = &\{b\} \{ε, ab, abab, ababab, …\}\\ =& \{b, bab, babab, bababab, …\}\\ L( (ba)^{\star}b) =& L((ba)^{\star}) L(b)\\ =& (L(ba))^{\star}L(b)\\ =& (L(b)L(a))^{\star} L(b)\\ =& \{ba\}^{\star} \{b\}\\ =& \{ε, ba, baba, bababa, …\} \{b\}\\ =&\{b, bab, babab, bababab, …\} \end{aligned}$$

  所以

  $$\begin{aligned} L(b(ab)^{\star})&= L( (ba)^{\star}b)\\ b(ab)^{\star}&=(ba)^{\star}b \end{aligned}$$

练习

证明

$$(a^{\star}b^{\star})^{\star}=(a|b)^{\star}$$

证明：

$$\begin{aligned} L((a^{\star}b^{\star})^{\star}) =&L(a^{\star}b^{\star})^{\star}\\ =&(L(a^\star)L(b^\star))^{\star}\\ =&(L(a)^\star L(b)^\star)^{\star}\\ =& (a^nb^m)^{\star}\\ =& (\{a\}\cup \{b\})^\star\\ L((a|b)^{\star}) =& (L(a|b))^{\star}\\ =&(L(a)\cup L(b))^{\star}\\ =&(\{a\}\cup \{b\})^\star \end{aligned}$$

所以

$$\begin{aligned} L((a^{\star}b^{\star})^{\star})&= L((a|b)^{\star})\\ (a^{\star}b^{\star})^{\star}&=(a|b)^{\star} \end{aligned}$$

词法规则的形式化——确定有限自动机(DFA)

确定有限自动机

• 对状态图进行形式化定义
• 确定有限自动机(Deterministic Finite Automata，DFA)$M$是一个五元式$M=(S, Σ, f, S_0, F)$，其中：
  • $S$: 有穷状态集
  • $Σ$：输入字母表(有穷)
  • $f$: 状态转换函数，为$S×Σ→S$的单值部分映射，$f(s,a)=s’$表示：当现行状态为$s$，输入字符为$a$时，将
    状态转换到下一状态$s’$，$s’$称为$s$的一个后继状态
  • $S_0∈S$是唯一的一个初态
  • $F⊆S$：终态集(可空)
• DFA表示为状态转换图
  • 假定DFA $M$含有$m$个状态和$n$个输入字符
  • 对应的状态转换图含有$m$个状态结点，每个结点顶多含有$n$条箭弧射出，且每条箭弧用$Σ$上的不同的输入字符来作标记
• 对于$Σ^{\star}$中的任何字$α$，若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记符连接成的字等于$α$，则称$α$为DFA $M$所识别(接收)
• DFA $M$所识别的字的全体记为$L(M)$
  • 

例子

DFA $M=( \{0，1，2，3\},\{a，b\},f,0,\{3\})$，其中$f$定义如下：

$$\begin{array}{lll} f(0, a)=1 & f(0, b)=2 \\ f(1, a)=3 & f(1, b)=2 \\ f(2, a)=1 & f(2, b)=3 \\ f(3, a)=3 & f(3, b)=3 \end{array}$$

词法规则的形式化——非确定有限自动机(NFA)

非确定有限自动机

• 定义：一个非确定有限自动机(Nondeterministic Finite Automata，NFA)$M$是一个五元式$M=(S, Σ, f, S_0, F)$，其中：
  • $S$: 有穷状态集
  • $Σ$：输入字母表(有穷)
  • $f$: 状态转换函数，为$S×Σ^{\star}→2^S$的部分映射
  • $S_0⊆S$是非空的初态集
  • $F⊆S$：终态集(可空)
• 从状态图看NFA 和DFA的区别
  • NFA可以有多个初态
  • 弧上的标记可以是$Σ^{\star}$中的一个字(甚至可以是一个正规式)，而不一定是单个字符
  • 同一个字可能出现在同状态射出的多条弧上
  • DFA是NFA的特例
  • 
• 对于$Σ^{\star}$中的任何字$α$，若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记字连接成的字等于$α$(忽略那些标记为$ε$的弧)，则称$α$为NFA $M$所识别(接收)
• NFA $M$所识别的字的全体记为$L(M)$

DFA和NFA

• 定义：对于任何两个有限自动机$M$和$M’$，如果$L(M)=L(M’)$，则称$M$与$M’$等价
• 自动机理论中一个重要的结论：判定两个自动机等价性的算法是存在的
• 对于每个NFA $M$存在一个DFA $M’$，使得$L(M)=L(M’)$
• DFA与NFA识别能力相同!